package offer.singleLinkedList;

/**
 * Description：
 * Author: zhangc
 * Date：2017/7/19 18:01
 */
public class MergeLinkedList17 {

    public static <T extends Comparable<? super T>> LinkedList<T> merge(LinkedList<T> left, LinkedList<T> right) {

        if (left.getValue() == null || right.getValue() == null)
            return left == null ? right : left;
        LinkedList<T> head = right, other = left, rtnHead ;
        if (left.getValue().compareTo(right.getValue()) <= 0) {
            head = left;
            other = right;
        }
        rtnHead = head;
        LinkedList temp;
        while (head.getNext() != null && other != null) {
            if (head.getNext().getValue().compareTo(other.getValue()) >= 0 ) {
                temp = other;
                other = other.getNext();
                temp.setNext(head.getNext());
                head.setNext(temp);
            }
            head = head.getNext();
        }
        if (head.getNext() == null) {
            head.setNext(other);
        }
        return rtnHead;
    }
}
